package com.skh.array;

/**
 * created by skh on 2019/6/23
 * 287.寻找重复数
 */
public class FindDuplicate {

	/*
	给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

	示例 1:

	输入: [1,3,4,2,2]
	输出: 2
	示例 2:

	输入: [3,1,3,4,2]
	输出: 3

	说明：
	不能更改原数组（假设数组是只读的）。
	只能使用额外的 O(1) 的空间。
	时间复杂度小于 O(n2) 。
	数组中只有一个重复的数字，但它可能不止重复出现一次。
	 */


	/*
	思路:
	二分查找：时间 O(NlogN) 空间 O(1)

	我们可以用二分法先选取n/2，按照抽屉原理，整个数组中如果小于等于n/2的数的数量大于n/2，说明1到n/2这个区间是肯定有重复数字的。
	比如6个抽屉，如果有7个袜子要放到抽屉里，那肯定有一个抽屉至少两个袜子。
	这里抽屉就是1到n/2的每一个数，而袜子就是整个数组中小于等于n/2的那些数。
	这样我们就能知道下次选择的数的范围，如果1到n/2区间内肯定有重复数字，则下次在1到n/2范围内找，否则在n/2到n范围内找。下次找的时候，还是找一半。

	注意

	我们比较的mid而不是nums[mid]

	因为mid是下标，所以判断式应为cnt > mid，最后返回min

	注意：弄清计算数量是nums[i]，而数量比较是 mid,而mid可以看成也是递增的。（每次比较的都是nums这个大范围中的数字）
	 */
	public int findDuplicate(int[] nums) {
		int min =0;
		int max = nums.length-1;
		while (min <= max) {
			//找到中间那个数
			int mid = min + (max-min)/2;
			int count =0;
			// 计算总数组中有多少个数小于等于中间数
			for (int i = 0; i < nums.length; i++) {
				if (nums[i] <= mid) {
					count++;
				}
			}

			// 如果小于等于中间数的数量小于中间数，说明后半部分必有重复
			if (count<=mid){
				min = mid+1;
			}else {
				// 否则前半部分必有重复
				max = mid-1;
			}
		}

		return min;
	}

}
